package 力扣.动态规划;
//给你两个数组 nums1 和 nums2 。
//
//请你返回 nums1 和 nums2 中两个长度相同的 非空 子序列的最大点积。
//
//数组的非空子序列是通过删除原数组中某些元素（可能一个也不删除）后剩余数字组成的序列，但不能改变数字间相对顺序。比方说，[2,3,5] 是 [1,2,3,4,5] 的一个子序列而 [1,5,3] 不是。
public class 两个字序列的最大点积 {
    public static void main(String[] args) {
        int[] nums1={2,1,-2,5};
        int[] nums2={3,0,-6};
        int i = maxDotProduct(nums1, nums2);
        System.out.println(i);
    }
    public static int maxDotProduct(int[] nums1, int[] nums2) {
        int m=nums1.length;
        int n=nums2.length;
        int[][] dp = new int[m + 1][n + 1];
        //将dp数组初始化为最小值
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[0].length; j++) {
                dp[i][j]= Integer.MIN_VALUE;
            }
        }
        for (int i = 1; i <m+1; i++) {
            for (int j = 1; j <n+1 ; j++) {
                dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
                dp[i][j]=Math.max(Math.max(0, dp[i - 1][j - 1]) + nums1[i - 1] * nums2[j - 1],dp[i][j]);
            }
        }
        return dp[m][n];
    }
}
